package datastructure_algorithm.linkedlist;

public class LinkedList<E> {

	private class Node {
		public E e;
		public Node next;

		public Node(E e, Node next) {
			this.e = e;
			this.next = next;
		}

		public Node(E e) {
			this(e, null);
		}

		public Node() {
		}

		@Override
		public String toString() {
			return e.toString();
		}
	}

	private Node dummyHead;
	private int size;

	public LinkedList() {
		dummyHead = new Node(null, null);
		size = 0;
	}

	public int getSize() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void addFirst(E e) {
		// no index check, faster
		dummyHead.next = new Node(e, dummyHead.next);
		size++;
//		add(0, e);
	}

	public void add(int index, E e) {
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("Illegal index");
		}

		Node prev = dummyHead;
		for (int i = 0; i < index; i++) {
			prev = prev.next;
		}
		prev.next = new Node(e, prev.next);
		size++;
	}

	public void addLast(E e) {
		add(size, e);
	}

	public E get(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Illegal index.");
		}

		Node cur = dummyHead.next;
		for (int i = 0; i < index; i++) {
			cur = cur.next;
		}
		return cur.e;
	}

	public E getFirst() {
		return get(0);
	}

	public E getLast() {
		return get(size - 1);
	}

	public void set(int index, E e) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Set failed. Illegal index.");
		}
		Node cur = dummyHead.next;
		for (int i = 0; i < index; i++) {
			cur = cur.next;
		}
		cur.e = e;
	}

	public boolean contains(E e) {
		Node cur = dummyHead.next;
		while (cur != null) {
			if (cur.e.equals(e)) {
				return true;
			}
			cur = cur.next;
		}
		return false;
	}

	public E remove(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Reomve failed. Illegal index.");
		}
		Node prev = dummyHead;
		for (int i = 0; i < index; i++) {
			prev = prev.next;
		}
		Node x = prev.next;
		prev.next = x.next;
//		x.next = null; // x will destroy when method done.???
		size--;

		return x.e;
	}

	public void removeElement(E e) {
		Node prev = dummyHead;
		while (prev.next != null) {
			if (prev.next.e.equals(e)) {
				break;
			}
			prev = prev.next;
		}
		if (prev.next != null) {
			Node delNode = prev.next;
			prev.next = delNode.next;
			delNode.next = null;
			size--;
		}
	}

	public E removeFirst() {
		return remove(0);
	}

	public E removeLast() {
		return remove(size - 1);
	}

	@Override
	public String toString() {
		return toString1();
	}

	public String toString2() {
		StringBuilder sb = new StringBuilder();
		sb.append("LinkedList: [");
		for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
			sb.append(cur + "->");
		}
		sb.append("null]");
		return sb.toString();
	}

	public String toString1() {
		StringBuilder sb = new StringBuilder();
		sb.append("LinkedList: [");
		Node cur = dummyHead.next;
		while (cur != null) {
			sb.append(cur + "->");
			cur = cur.next;
		}
		sb.append("null]");
		return sb.toString();
	}

	private String toString0() {
		StringBuilder sb = new StringBuilder();
		sb.append("LinkedList: [");
		Node node = dummyHead.next;
		for (int i = 0; i < size; i++) {
			sb.append(node);
			if (node.next != null) {
				sb.append(", ");
			}
			node = node.next;
		}
		sb.append("]");
		return sb.toString();
	}

}
